이번 문제는 2017년 하반기로 추정(?) 되는 SW 역량테스트 기출 복원문제 입니다. 2개의 팀에 멤버들을 각각 나누어 편성할 때, 팀에 같이 있음으로써 생기는 능력치들을 모두 합하였을 때 양 팀의 능력치가 차이가 최소가 되는 경우를 찾으면 됩니다.
문제를 얼핏 보았을 때는 특정한 해법을 찾아야 되나 싶은 생각이 들 수 있습니다. 하지만 왠지 이런 문제는 모든 경우를 다 따져보아야 할 것 같은 느낌이 듭니다. 그렇지만 제한된 시간내에 문제가 풀릴 수 있을 까 싶은 생각이 듭니다. 그러므로 항상 문제를 풀 때 가장 중요하게 파악해야 하는, 문제의 input 범위를 체크합니다. 인원수는 총 20명이고, 20명을 양쪽 팀에 골고루 분배해야 합니다. 즉, $C(20,10) = 184756$ 가지의 경우의 수를 계산해 봐야 함을 알 수 있습니다. 전처리를 좀 더 잘한다면, A팀에서 같이 만나던, B팀에서 같이 만나던 상관 없으므로 전체 확인해야 할 경우의 수를 $1/2$ 줄일 수 있습니다.
각 멤버들간의 능력치 총합을 구하려면 2중 for문을 이용해 계산할 수 있습니다. 20명이 최대이므로, 양 팀의 능력치 총합은 최대 100번의 for문 연산으로 계산할 수 있습니다. 따라서 이 문제는 제한시간 내에 충분히 완전탐색할 수 있음이 확인되었습니다. 문제를 풀 때는 재귀적으로 dfs문을 이용하면 편리합니다. 다음과 같이 설계하여 함수를 만들 수 있습니다.
1. 왼쪽 팀에 들어갈 수 있다면 왼쪽 팀에 추가 후 다음 진행
2. 오른쪽 팀에 들어갈 수 있다면 오른쪽 팀에 추가 후 다음 진행
3. 모든 인원이 각 팀에 분배되었다면, 능력치 총합을 계산 후 min 값 갱신
여기까지만 생각하고 코딩하여 제출한 결과 24ms가 나와 충분히 pass 할 수 있음을 알 수 있습니다. algotirhm 헤더 파일을 include 하여 사용할 수 있다면, next_permutation 등을 이용하여 코딩할 수 있습니다.
※해당 소스코드는 참고용이며, 최적화 된 공식 솔루션 소스가 아닙니다. 이 소스를 그대로 복사하여 이용, 또는 제출하는 행위에 대한 불이익은 책임지지 않습니다.
#include <iostream>
using namespace std;
int n, hn, score[20][20], lt[10], rt[10], answer = 2e9;
int min(int a, int b) {
return a < b ? a : b;
}
int abs(int a) {
return a < 0 ? -a : a;
}
void dfs(int idx, int lidx, int ridx) {
if (idx == n) {
int left = 0, right = 0;
for (int i = 0; i < hn; i++) {
for (int j = 0; j < hn; j++) {
left += score[lt[i]][lt[j]];
right += score[rt[i]][rt[j]];
}
}
answer = min(answer, abs(left - right));
return;
}
if (lidx < hn) {
lt[lidx] = idx;
dfs(idx + 1, lidx + 1, ridx);
}
if (ridx < hn) {
rt[ridx] = idx;
dfs(idx + 1, lidx, ridx + 1);
}
}
int main() {
cin >> n;
hn = n / 2;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> score[i][j];
}
}
dfs(0, 0, 0);
cout << answer;
}